# 考的是位移和 递归
class Solution:
    def divide1(self, dividend: int, divisor: int) -> int:
        if dividend==-2147483648:
            if divisor==-1:
                return 2147483647
            elif divisor==1:
                return -2147483648
        elif dividend==2147483647:
            if divisor==-1:
                return -2147483648
            elif divisor==1:
                return 2147483647

        flag1=1
        flag2=1
        sumn = 0
        if  dividend<0:
            flag1=-1
            dividend=-dividend
        if  divisor<0:
            flag2=-1
            divisor=-divisor
        while dividend>=divisor:
            sumn+=1
            dividend-=divisor
        return sumn*flag1*flag2


    def divide2(self, dividend: int, divisor: int) -> int:
        i,flag1,flag2=0,abs(dividend),abs(divisor)
        if flag1==0 or flag1<flag2:
            return 0
        while flag2<=flag1:
            i+=1
            flag2=flag2<<1
        res=(1<<(i-1))+self.divide2(flag1-(flag2>>1),abs(divisor))
        if (dividend ^ divisor) < 0:
            res=-res
        if res>2147483647:
            return 2147483647
        return res

    def divide(self, dividend, divisor):
        i, a, b = 0, abs(dividend), abs(divisor)
        if a == 0 or a < b:
            return 0

        while b <= a:
            b = b << 1
            i = i + 1
        else:
            res = (1 << (i - 1)) + self.divide(a - (b >> 1), abs(divisor))
            if (dividend ^ divisor) < 0:
                res = -res
            return min(res, (1 << 31) - 1)





lll=Solution()
print(lll.divide2(125421, 3))
